// https://www.lintcode.com/problem/median/

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: An integer denotes the middle number of the array
     */
    public int median(int[] nums) {
        // write your code here
        return median(nums, 0, nums.length - 1, (nums.length + 1) / 2);
    }
    
    private int median(int[] nums, int start, int end, int t_pos) {
        if (start >= end) {
            return nums[start];
        }
        int idx = start, tmp;
        for (int i = start + 1; i <= end; ++i) {
            if (nums[i] < nums[start]) {
                ++idx;
                tmp = nums[idx];
                nums[idx] = nums[i];
                nums[i] = tmp;
            }
        }
        tmp = nums[idx];
        nums[idx] = nums[start];
        nums[start] = tmp;
        if ((idx - start + 1) == t_pos) {
            return nums[idx];
        }
        else if ((idx - start + 1) > t_pos) {
            return median(nums, start, idx - 1, t_pos);
        }
        else {
            return median(nums, idx + 1, end, t_pos - (idx - start + 1));
        }
    }
}